//
// Created by ASUS on 2024/2/1.
//
#include<bits/stdc++.h>
using namespace std;

vector<double> findMid(vector<int>&a){
	priority_queue<int> qMax;
	priority_queue<int,vector<int>,greater<int>> qMin;
	vector<double> ans(a.size());
	for(int i=0;i<(int)a.size();i++){
		if(qMax.empty()||a[i]<=qMax.top()){
			qMax.push(a[i]);
			if (qMin.size() + 1 < qMax.size()) {
				qMin.push(qMax.top());
				qMax.pop();
			}
		} else {
			qMin.push(a[i]);
			if (qMin.size() > qMax.size()) {
				qMax.push(qMin.top());
				qMin.pop();
			}
		}
		if (qMax.size() > qMin.size()) {
			ans[i]= qMax.top();
		}
		else ans[i]=(qMax.top() + qMin.top()) / 2.0;
	}
	return ans;
}


int main(){
	vector<int> arr{1,2,3,6,1,0,0,9,6,5,2};
	auto ans=findMid(arr);
	for(double x:ans) cout<<x<<" ";
	return 0;
}
